\documentclass[11pt,twoside,a4paper]{article}

\usepackage[french]{babel}
%\usepackage{a4}
\usepackage{fullpage}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsmath, amsthm}
\usepackage{amsfonts,amssymb}
\usepackage{float}
\usepackage{graphics}
\usepackage{graphicx}
\usepackage[thinlines,thiklines]{easybmat}
\usepackage{multirow}
%\usepackage{algorithmic}
%\usepackage{algorithm}

% Style bibliographique
\bibliographystyle{plain}
%--- Definitions de nouvelles commandes ---
\newcommand{\N}{\mathbb{N}} % les entiers naturels
\newcommand{\Z}{\mathbb{Z}} % les entiers relatifs
\newcommand{\Q}{\mathbb{Q}} % les rationnels
\newcommand{\R}{\mathbb{R}} % les rationnels
\newcommand{\F}{\mathbb{F}} % un corps fini
\newcommand{\K}{\mathbb{K}} % un corps
\newcommand{\p}{\mathfrak{p}} % un p gothik
\newcommand{\M}{\mathcal{M}}
\newcommand{\Cl}{\operatorname{Cl}}
\newcommand{\OO}{\mathcal{O}}
\newcommand{\OK}{\mathcal{O}_K}
\newcommand{\courbe}{\mathcal{C}} % une courbe avec un joli C
\newcommand{\jac}{\operatorname{Jac}(\mathcal{C})} %la jacobienne
\newcommand{\jacone}{\operatorname{Jac}(\mathcal{C}_1)} %la jacobienne
\newcommand{\jactwo}{\operatorname{Jac}(\mathcal{C}_2)} %la jacobienne
\newcommand{\Nm}{\mathcal{N}_{\K/\Q}}
\newcommand{\ag}{\mathfrak{a}}

\newtheorem{definition}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{heuristic}{Heuristic}
\newtheorem{proposition}{Proposition}
\newtheorem{corollary}{Corollary}
\newtheorem{notation}{Notation}
\newtheorem{example}{Example}
%\renewcommand{\algorithmicrequire}{\textbf{Input:}}
%\renewcommand{\algorithmicensure}{\textbf{Output:}}

%\newcommand{\algorithmicreturn}{\textbf{return}}
%--- Pour le titre ---
\title{Research plan}
\author{Jean-Fran\c{c}ois Biasse \\
biasse@lix.polytechnique.fr}
\date{}
%============================= Corps =================================
\begin{document}
\maketitle            % écrit le titre
%\tableofcontents      % écrit la table des matières



\section{Introduction}

%Mon programme de recherche pour les années à venir concerne le développement d'algorithmes efficaces pour résoudre 
%des problèmes de théorie des nombres et de calcul formel, ainsi que l'étude de leurs applications à la cryptologie. 
%Depuis la fin des année 1970 et l'avènement des cryptosystèmes à clef publique~\cite{DH, RSA}, une grande partie de 
%la recherche en calcul formel se focalise sur les problématiques ayant trait à la sécurité informatique. La sécurité 
%des échanges et du stockage de données repose sur 
%la difficulté présumée de certains problèmes mathématiques. Ainsi, le problème dit du \og logarithme discret \fg est 
%à la base de l'authentification et de l'échange de clef sur les réseaux numériques tels que l'internet, tandis que la 
%difficulté de factoriser des entiers de grande taille protège les échanges dans le cadres des protocoles dits 
%\og à clef publique \fg. L'efficacité de ces primitives cryptographique repose sur la réalisation de nombreuses 
%opérations arithmétiques dans des structures algébriques, et revêt un caractère crucial dans les contextes où les 
%ressources sont limitées, comme c'est le cas pour les systèmes embarqués.
My research plan for the coming years concerns the development of efficient algorithms to solve number theoretic 
and computer algebra problems with applications to cryptology and coding theory. Since the end of the 1970's and 
the introduction of the first public-key cryptosystems~\cite{DH, RSA}, a large part of the research in computer 
algebra has focused on information security-related problems. The security of data exchange and data storage 
relies on the assumed difficulty of certain mathematical problems. This way, the ``discrete logarithm problem'' 
is the basis of authentication and key exchange implementations in digital networks such as the internet, whereas the hardness 
of factoring integers of a large size protects data exchange in so-called ``public-key'' protocols. The efficiency 
of a variety of cryptographic primitives relies on arithmetic operations in algebraic structures, and is crucial
contexts where the resources are limited, e.g., embedded systems. 


%L'étude d'algorithmes de résolution de problèmes sur lesquels peuvent reposer des cryptosystèmes 
%intersecte bien souvent les préoccupations parfois anciennes des théoriciens des nombres, tout en %fournissant des défis aux chercheurs en calcul formel. Par exemple, la célèbre hypothèse de Riemann 
%qui est une conjecture non prouvée remontant au milieu du XIXième siècle permet d'évaluer la 
%distribution des nombres premiers, contribuant ainsi à l'analyse de la complexité du crible algébrique, meilleur algorithme de factorization de grands entiers connus à ce jour. Parmi les problèmes de 
%théorie des nombres utilisés en cryptologie, le logarithme discret dans les jacobiennes de courbes algébriques apparaît comme l'un des plus prometteurs pour les cryptosystèmes des années à venir. En effet, il permet l'emploi de clefs de taille plus petites que RSA, son concurent direct, pour une sécurité équivalente. De plus, les meilleures attaques contre le problème du logarithme discret dans les jacobiennes de courbes algébriques sont de complexité exponentielle dans les classes de courbes de genre fixé tandis que le crible algébrique permet la factorisation d'entiers en complexité heuristique sous-exponentielle $L(1/3,O(1))$.
The study of algorithms for attacking the difficult problems on which cryptosystems rely often intersects 
the sometimes old preocupations of number theorists, while providing challenges to researchers in computer 
algebra. For example, the famous Riemann hypothesis, which is an unproved conjecture dating from the 
middle of the nineteeth century, describes the distribution of prime numbers, essential 
to the analysis of best known algorithm for factoring large integers, namely the number field sieve. 
Amongst the number theoretic problems used in cryptology, the discrete logarithm in Jacobians of algebraic 
curves appears to be one of the most promising for describing the cryptosystems in the comings years. Indeed, it 
allows to use shorter keys than its direct competitor RSA for an equivalent level of security. 
Furthermore, the best known attacks against the discrete logarithm problem in the Jacobian of hyperelliptic 
curves are exponential in complexity for classes of curves of fixed genus, whereas the number field sieve 
allows the factorization of integers in heuristic sub-exponential time  $L(1/3,O(1))$.


%Je compte m'intéresser à des sujets différents ayant pour point commun des applications à la cryptographie et à la théorie des codes. Pour cela, je m'appuierai sur les résultats que j'ai obtenus durant ma thèse dans le domaine de la théorie algorithmique des nombres, ainsi que ceux obtenus en calcul formel durant mes recherches postdoctorales. Les axes principaux que je souhaite développer sont la résolution du logarithme 
%discret dans les corps de fonctions, l'étude de la mise en forme canonique de bases de modules, et la multiplication complexe, qui est actuellement un sujet de préoccupations important dans la communauté cryptologique.

I intend to focus on different topics that have in common the possibility of applications to cryptology 
and coding theory. For that, I will rely on the results I obtained in thesis in the domain of 
algorithmic number theory, as well as on those obtained in computer algebra during my postdoctoral 
research. The main axes I would like to develop are the resolution of the discrete logarithm problem 
in function fields, the study of the computation a basis of a module in canonical form, and complex 
multiplication, which is currently an important subject of preocupation in the cryptographic 
community.   



\section{Discrete logarithm in function fields}\label{sec:log_disc}

%Un courbe algébrique $\courbe$ sur un corps fini $\F_q$ est le lieu d'annulation d'un polynôme bivarié 
%donné par 
%$$P_{\courbe}(X,Y) = 0,$$
%où $P_{\courbe}\in\F_q[X,Y]$. Lorsque le degré en $Y$ est 2, on parle de courbe hyperelliptique. Dans ce cas, 
%le genre , qui est un invariant de $\courbe$ définit par le degré en $X$ permet une classification. Une 
%courbe sur un corps fini permet de définir un groupe fini $\jac$ de manière analogue à la définition du
%groupe de classes d'idéaux d'un corps de nombres. Ici, $\F_q(X)$ joue le rôle de $\Q$, et le corps de 
%fonctions $\F_q(X)[Y]/(\courbe)$ est l'analogue d'un corps de nombre $K/\Q$. La Jacobienne de $\courbe$ 
%est alors définie par 
%$$\jac := \{ \text{diviseurs de degré 0 de } \courbe\}/\{\text{diviseurs principaux}\}.$$ 
%La Jacobienne de $\courbe$ est un groupe fini, et le borne de Hasse indique que 
%$$\#\jac\approx \#\F_q^g.$$
%La difficulté du problème du logarithme discret dans $\jac$ est à la base de nombreux cryptosystèmes. 
%En particulier, le cas des courbes elliptiques ($g=1$) a attiré l'attention de la communauté cryptologique 
%par la simplicité des opérations arithmétiques, et l'efficacité des implantations. Il y a cependant un 
%intérêt croissant pour une meilleure compréhension des courbes hyperelliptique de genre $g\geq 2$, et pour 
%les corps de fonctions de degré plus important d'une manière générale, en particulier dans l'éventualité 
%de la découverte de nouvelles attaques ciblant des classes précises de courbes.
An algebraic plane curve $\courbe$ over a finite field $\F_q$ is the locus of the equation 
$$P_{\courbe}(X,Y) = 0,$$
where $P_{\courbe}\in\F_q[X,Y]$. For hyperelliptic curves, the degree in $Y$ is 2. In this 
case, the genus, which is an invariant of $\courbe$ defined by the degree in $X$ of $P$, allows to classify 
them. To a curve over a finite field one associates the finite group $\jac$ in an way that is 
analogous to the definition of the ideal class group of a number field. Here, $\F_q(X)$ plays the role 
of $\Q$, and the function field $\F_q(X)[Y]/(P_\courbe)$ is the analogue of a number field $K/\Q$. The 
Jacobian of $\courbe$ is then defined by 
$$\jac := \{ \text{degree 0 divisors of } \courbe\}/\{\text{principal divisors}\}.$$
The Jacobian of $\courbe$ is a finite group, and the Hasse bound indicates that 
$$\#\jac\approx \#\F_q^g = q^g.$$
The hardness of the discrete logarithm problem in $\jac$ is at the basis of many cryptosystems. 
In particular, the case of elliptic curves ($g=1$) has drawn the attention of the cryptographic 
community by the simplicity of the arithmetic operations and the efficiency of implementations. However, 
there is a growing interest for a better comprehension of hyperelliptic curves of genus $g\geq2$, and for 
function fields of a larger degree in general, in particular, in the event of the discovery of new 
attacks targetting specific classes of curves. 


\paragraph{Quadratic sieve}
%Les meilleurs algorithmes actuels pour la résolution du problème du logarithme discret dans les courbes hyperelliptiques sont basé sur la stratégie de la marche aléatoire. Cependant, Flassenberg et Paulus on introduit dans~\cite{FlaPau} un algorithme pour résoudre ce problème basé sur le crible quadratique. Cet algorithme utilise les mêmes méthodes de génération de relations que celle introduite par Jacobson~\cite{pell} dans le contexte des corps de nombres, et que j'ai utilisées et améliorées dans~\cite{biasse_quad,BiaJac10,BiaJacSil10}. Il s'agit de traiter l'anneau des coordonées
%$\F_q[X][Y]/(\courbe)$ comme un ordre dans un corps de nombres quadratique. Les relations dans $\jac$ sont obtenues par la recherche de valeurs friables de formes quadratiques 
%$$\phi(U) = a(X)U^2 + b(X)U + c(X)\in \F_p[X][U].$$
%Cette recherche s'effectue avec un équivalent de l'algorithme du \textit{crible quadratique}[?]. 
%Les seules implantations existantes de cet algorithme dans le cas des corps de fonctions ne sont 
%efficaces que dans le cas des courbes de grand genre~\cite{velichka}. La plupart des améliorations 
%des méthodes basées sur le crible quadratique que j'ai développées pour les corps quadratiques devraient avoir un impact comparable dans le cas des corps de fonction, et en particulier dans les jacobiennes de courbes hyperelliptiques. Elles devraient notamment contribuer à baisser le genre minimal pour lequel le crible devient plus efficace que la marche aléatoire.
The best current algorithms for solving the discrete logarithm problem in hyperelliptic curves 
are based on the random walk strategy. However, Flassenberg and Paulus introduced in~\cite{FlaPau} 
an algorithm for solving this problem based on the quadratic sieve. This algorithm uses the same 
methods for generating relations as these described by Jacobson~\cite{pell} in the context of number 
fields, and that I used and improved in~\cite{biasse_quad,BiaJac10,BiaJacSil10}. It consists of treating 
the coordinate ring $\F_q[X][Y]/(P_\courbe)$ as an order in a quadratic number field. The relations in 
$\jac$ are obtained with smooth values of quadratic forms
 $$\phi(U) = a(X)U^2 + b(X)U + c(X)\in \F_p[X][U].$$
Finding smooth values of $\phi(U)$ can be done witha version of the \textit{quadratic sieve}~\cite{pomerance_quad_sieve}. 
The existing implementations of this algorithm in the context of function fields are 
only efficient for curves of high genus~\cite{velichka}. Most of the improvements in the methods based on 
the quadratic sieve that I developed for quadratic number fields should have a comparable impact in the 
case of function fields, and in particular, in the Jacobian of hyperelliptic curves. Specifically, they should 
 contribute to lower the maximal genus for which the sieve becomes more efficient than the 
random walk strategy.

\paragraph{Applications to cryptology}
%L'amélioration des performances pour les courbes de grand genre est intéressante du point de vue de la théorie des nombres, et elle peut aussi avoir des applications cryptographiques par des chemins détournés. En effet, il est possible de transporter le problème du logarithme discret de la jacobienne d'une courbe elliptique vers celle d'une courbe hyperelliptique de plus grand genre via la \og descente de Weil\fg. Naturellement, les courbes elliptiques sujettes à ce type d'attaques ont été bannies de tout usage cryptographique, mais cette faiblesse a été exploitée par Teske~\cite{teske} pour décrire d'un point de vue théorique un cryptosystème dans lequel l'utilisateur doit résoudre des instances du problème du logarithme discret dans la jacobienne d'une courbe de genre élevé. Les tailles mises en jeu ont pour l'instant empêché toute réalisation pratique d'un tel cryptosystème, mais l'amélioration de la recherche des relations via les méthodes de crible dans les courbes de grand genre pourrait lever cette obstruction.
The improvement of performance for high genus curves is interesting from a theoretical point of view, 
but it can also have cryptographic applications. Indeed, it is possible to transport the 
discrete logarithm problem from the Jacobian of an elliptic curve to the one of a hyperelliptic curve 
of a higher genus via ``Weil descent''. Naturally, elliptic curves subject to this kind of attacks 
were banished from any cryptographical use. However, this weakness was exploited by Teske~\cite{teske} to 
describe from a theoretical point of view a cryptosystem in which the user has to solve instances of the 
discrete logarithm problem in the Jacobian of a high genus curve. The sizes involved have for now prevented 
any practical realization of such a cryptosystem, but the improvement of the search for relations via 
sieving-based methods could lift this obstruction.

\paragraph{Number field sieve}

%L'analogie entre les corps de fonctions de degré 2 et les corps quadratiques permet l'adaptation 
%des techniques basées sur le crible quadratique pour le calcul de relations, et donc la résolution 
%du problème du logarithme discret. Il est naturel de s'interroger sur ce qu'il en est des corps de 
%fonctions de degré supérieur. En effet, j'ai récemment décrit, en collaboration avec Fieker, un 
%algorithme analogue au crible algébrique~\cite{NFS} pour le calcul de relations dans le groupe de 
%classes d'idéaux de corps de nombres de degré aritraire. Cet algorithme, qui sera présenté 
%dans~\cite{biasse_NFS}, a été implanté dans le logiciel de calcul formel Magma~\cite{magma}, et 
%s'est révélé très efficace pour les corps de nombres de petit degré. La recherche de relations dans 
%le groupe de classes d'un corps de fonction de degré $n$ peut se faire par le calcul de valeurs friables 
%de polynômes de la forme 
%$$\phi(U,V) = a_n(X)U^n + a_{n-1}(X)U^{n-1}V + \cdots + a_1(X)V^n\in F_q[X][U,V].$$
%Il est permis d'espérer 
%qu'une adaptation de ces techniques de crible pour la recherche de valeurs friables dans les corps de
%fonctions permettrait d'atteindre des résultats comparables lorsque le degré en $Y$ de $\courbe$ est 
%faible.  
The analogy between degree 2 function fields and quadratic number fields allows the adaptation 
of quadratic sieve-based techniques for computing relations, and thus the resolution of the 
discrete logarithm problem. It is natural to ask whether or not a similar analogy is possible in 
higher degree. Indeed, I recently described, in collaboration with Fieker, an algorithm analogous to 
the number field sieve~\cite{NFS} for computing relations in the ideal class group of general number 
fields. This algorithm, which will be presented in~\cite{biasse_NFS}, was implemented in the computer 
algebra software Magma~\cite{magma}, and proved itself to be very efficient for number fields of 
small degree. The search for relations in the ideal class group of a function field of degree $n$ 
can be done by looking at smooth values of polynomials of the form
$$\phi(U,V) = a_n(X)U^n + a_{n-1}(X)U^{n-1}V + \cdots + a_1(X)V^n\in F_q[X][U,V].$$
One can hope that the adaptation of sieving techniques to the search for smooth values in function 
fields should allow to achieve similar results when the degree in $Y$ of $\courbe$ is low.

\section{Efficient algorithms for canonical form computation}

%Étant donné un anneau $R$, et un $R$-module de dimension $n$, une tâche essentielle en calcul formel est le calcul d'une 
%base $b_1,\cdots,b_n$ jouissant de bonnes propriétés et telle que 
%$$M = R b_1 + \cdots + R b_n.$$
%Par exemple. dans le cas $R = \Z$, l'algorithme LLL~\cite{LLL} permet notamment de trouver une base de $M$ ayant de courts 
%vecteurs, permettant ainsi de faciliter la résolution de la recherche du plus court vecteur dans $M$, ou bien la recherche 
%du vecteur le plus proche dans $M$. Cet algorithme a de nombreuses applications en cryptographie des 
%réseaux. Un autre exemple typique est la mise sous forme de Hermite (HNF) d'un 
%système de générateurs du $\Z$-module $M$ des relations d'un groupe $(G,*)$. Soient $(g_1,\cdots,g_n)$ des 
%générateurs de $G$, à chaque relation de la forme 
%$$g_1^{e_1}*\cdots*g_n^{e_n} = 1_G,$$
%correspond un vecteur $(e_1,\cdots,e_n)\in M$. Le calcul d'une base en forme HNF de $M$ consiste en 
%l'applications d'opérations unimodulaire à la matrice représentant les générateurs de $M$ afin 
%de la mettre sous forme triangulaire. Cela permet notamment 
%le calcul de la structure de $G$, et la résolution du problème du logarithme discret dans $G$. Dans le 
%cas où $G = \jac$, les algorithme de mise sous forme canonique ont un impact direct sur les axes de 
%recherche développés au \S~\ref{sec:log_disc}.
Given a ring $R$ and an $R$-module $M$ of dimension $n$, an essential task in computer algebra is the 
computation of $b_1,\cdots,b_n$ enjoying good properties and such that
$$M = R b_1 + \cdots + R b_n.$$
For example, in the case $R = \Z$, the LLL algorithm~\cite{LLL} allows to find a basis of $M$ consisting short vectors, thus 
facilitating the search for the shortest vector of $M$. This algorithm has a lot of applications in lattice-based 
cryptology. Another typical example is the Hermite Normal Form (HNF) computation of a system of generators of the
$\Z$-module $M$ of relations in an abelian group $G$. Let $(g_1,\cdots,g_n)$ be generators of $G$, each relation of the 
form 
$$g_1^{e_1}\cdots g_n^{e_n} = 1,$$
corresponds to a vector $(e_1,\cdots,e_n)\in M$. The computation of an HNF basis of $M$ consists of unimodular operations 
on the matrix representing the generators of $M$ leading to a triangular form. This occurs in particular during the 
computation of the structure of $G$, and the computation of discrete logarithms in $G$. In the case where $G = \jac$, 
the algorithms for computing canonical forms have a direct impact on the axes of research developed in \S~\ref{sec:log_disc}. 


\paragraph{Hermite Normal Form}

%Les implantations actuelles de la mise sous forme HNF d'une matrice à coefficients dans $\Z$  
%prennent peu ou pas en compte les spécificité liés aux applications à la théorie des nombres et à la 
%cryptologie. En effet, des résultats récents sont venus améliorer la complexité 
%du calcul de la HNF dans le cas général~\cite{PerStein11,Sto_quasi_opt}, mais le cas spécifique 
%des matrices traitées pendant les algorithmes de calcul d'index a été traité pour la dernière fois
%dans~\cite{JacobsonHNF}. J'ai réalisé une implantation basées sur les idées de~\cite{JacobsonHNF} dans 
%la bibliothèque C++ linbox\cite{linbox} en collaboration avec les membres de l'équipe CASYS au laboratoire 
%Jean Kunzmann de Grenoble. Cependant, cet angle de recherche mérite d'être approfondi, en mettant notamment
%l'accent sur les améliorations pratiques heuristiques. 
The current implementations of the Hermite Normal computation of a matrix with integer coefficients do not take into 
account the special features of matrices arising in applications to number theory and cryptology. Indeed, recent results 
improved the complexity of computing the HNF of random matrices~\cite{PerStein11,Sto_quasi_opt}, but the 
specific case of the matrices processed during index calculus algorithm was last studied in~\cite{JacobsonHNF}. 
I realized an implementation based on the ideas of~\cite{JacobsonHNF} in the C++ library linbox~\cite{linbox} 
in collaboration with the members of the CASYS team of the Jean Kunzmann Institute in Grenoble. However, this 
axis of research deserves to be investigated further, in particular by emphasising practical improvements. 

%En ce qui concerne la complexité théorique, de nombreux problèmes d'algèbre linéraires sur les matrices polynomiales 
%carrées peuvent être 
%désormais résolus par des algorithmes en complexité $\tilde{O}(n^{\omega}d)$, où $\tilde{O}$ dénote la 
%complexité amortie (c'est à dire sans les facteurs logarithmiques), $n$ la dimension de la matrice et 
%$d$ une borne sur les degrés des entrées. Citons par exemple la résolution de systèmes linéaires par 
%lift $p$-adique, le calcul de déterminant, le calcul de forme normale de 
%Smith~\cite{Sto02_lift,Sto03_lift}, la réduction rapide de ligne de~\cite{Giorgi_pol_mat}, ainsi que 
%le calcul d'une base approximante minimale~\cite{Giorgi_pol_mat,arne}. Il est aussi notable que 
%le calcul explicite de l'inverse d'une matrice, dont la taille est en $\Omega(n^3 d)$ peut être réalisé 
%en temps quasi-optimal $\tilde{O}(n^3d)$ (voir~\cite{villard_inv_pol_mat,Sto_inv_mat}). 
%Récemment~\cite{Sto_quasi_opt}, Storjohann et Gupta ont montré que la HNF d'une matrice polynomiale 
%pouvait être calculée en temps $(n^3d)^{1+o(1)}$. Ainsi que mentionné dans~\cite{Sto_quasi_opt}, malgrès 
%l'espoir suscité par l'existence d'algorithmes optimaux pour les problèmes d'algèbre linéaire connexes, 
%l'élaboration d'un algorithme en $\tilde{O}(n^{\omega}d)$ pour le calcul de la HNF nécessitera de 
%nouvelles idées. Je souhaite étudier les méthodes permettant le rapprochement des performances des 
%algorithmes de mise en forme HNF vers le temps optimal. 
Concerning the theoretical complexity, many linear algebra problems on square polynomial matrices can now be solved 
by algorithms in complexity $\tilde{O}(n^{\omega}d)$, where $\tilde{O}$ denotes the softened complexity (that 
is to say without logarithmic factors), $n$ the dimension of the matrix and $d$ a bound on the degree of the 
entries. Let us mention, for example, high order lifting based linear system solving, determinant computation, 
Smith normal form computation~\cite{Sto02_lift,Sto03_lift}, the fast row reduction of~\cite{Giorgi_pol_mat}, 
as well as the computation of a minimal approximant basis~\cite{Giorgi_pol_mat,arne}. It is 
even known that the explicit inverse of a matrix, whose size is in $\Omega(n^3 d)$ can be computed in nearly 
optimal time  $\tilde{O}(n^3d)$ (see~\cite{villard_inv_pol_mat,Sto_inv_mat}). Recently~\cite{Sto_quasi_opt}, 
Gupta and Storjohann showed that the HNF of a polynomial matrix could be computed in time $(n^3d)^{1+o(1)}$. 
As stated in~\cite{Sto_quasi_opt}, despite the hope induced by the existence of optimal solutions to related 
linear algebra problem, the elaboration of an algorithm in $\tilde{O}(n^{\omega}d)$ for the computation of the 
HNF will need new ideas. I would like to explore the methods allowing to bring the performances of HNF algorithms 
closer to optimal.

\paragraph{Pseudo-bases of $\OK$-modules}

%Un $\OK$-module $M\subseteq K^l$, où $K$ est un corps de nombres et $\OK$ son 
%anneau des entiers, peut être décrit par une \textit{pseudo-base}, c'est à dire des idéaux fractionnaires 
%$(\ag_i)_{i\leq n}$ et des éléments $(A_i)_{i\leq n}$ de $K^l$ tels que 
%$$M = \ag_1 A_1 \oplus \cdots \oplus \ag_n A_n.$$
%Indépendamment des propriétés de $M$, la taille des $\ag_i$ et des $A_i$ peut être arbitrairement grande.
%La construction d'une bonne base pour un $\OK$-module  a reçu dernièrement un attention considérable de la part de la communauté 
%scientifique. En effet, les $\OK$-modules interviennent en cryptographie basée sur les 
%réseaux~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, où la sécurité des 
%cryptosystèmes repose sur la difficulté de trouver le vecteur le plus court, ou le vecteur le plus proche. 
%La forme normale de Hermite pour les $\OK$-modules, décrite par 
%Cohen~\cite[Chap. 1]{cohen2} intervient dans les calculs de base réduite, notamment au travers 
%de l'algorithme de Fieker et Stehl{\'e}~\cite{stehle_fieker_LLL}, et a par conséquent 
%des applications en cryptographie et en théorie des codes. J'ai récemment décrit~\cite{pseudo_HNF} 
%le premier algorithme en complexité polynomiale pour le calcul de HNF pour un $\OK$-module. Il 
%est essentiellement l'équivalent de l'algorithme de Kannan-Bachem~\cite{KannBach}, décrit il y a plus 
%de 30 ans. Il est raisonnable d'espérer généraliser dans un premier temps 
%les algorithmes les stratégies les plus efficaces connues pour les entiers, notamment 
%l'algorithme de Micciancio~\cite{MicWar01}, celui de Storjohann et al.~\cite{JacobsonHNF} et 
%l'approche modulaire de Pernet et Stein~\cite{PerStein11}. Dans un deuxième temps, il sera intéressant 
%de s'interroger sur la possibilité de se rapprocher des performances optimales, à l'instar de la 
%HNF classique.
An $\OK$-module $M\subseteq K^l$, where $K$ is a number field and $\OK$ its ring of integers, can be described 
by a \textit{pseudo-basis}, that is to say fractional ideals $(\ag_i)_{i\leq n}$ and elements $(A_i)_{i\leq n}$ of 
$K^l$ such that 
$$M = \ag_1 A_1 \oplus \cdots \oplus \ag_n A_n.$$
Inependently of the properties of $M$, the size of the $\ag_i$ and of the $A_i$ can be arbitrarily large. The 
construction of a good basis for an $\OK$-module recently recieved a lot of attention from the scientific 
community. Indeed, $\OK$-modules occur in lattice-based cryptography~\cite{LyuMic06icalp,Mic02cyclic,Mic07cyclic, RosenTCC,SSTX09}, 
where the security of the cryptosystems relies of the difficulty to the the shortest vector or the closest vector. 
The Hermite form for $\OK$-modules, described by Cohen~\cite[Chap. 1]{cohen2} occurs in the computation of a reduced 
basis, in particular through the algorithm of Fieker and Stehl{\'e}~\cite{stehle_fieker_LLL}, and thus has applications 
in cryptography and coding theory. I recently described~\cite{pseudo_HNF}, in collaboration with Fieker, the first 
polynomial time algorithm for computing hte HNF of an $\OK$-module. It is essentially the equivalent of the algorithm 
of Kannan and Bachem~\cite{KannBach}, described more than 30 years ago. First, it is reasonable to hope to generalize 
the best known strategies for integer matrices, in particular Micciancio's algorithm~\cite{MicWar01}, the one of 
Storjohann et al.~\cite{JacobsonHNF} and the modular approach of Pernet and Stein~\cite{PerStein11}. Then, it will 
be interesting to study the possibility of bringing the performances of these algorithm closer to the optimal time, 
as for the traditional HNF. 


\paragraph{Parallel aspects}

%L'augmentation de la puissance de calcul des machines se fait désormais plus par l'ajout de nouveaux 
%coeurs plutôt que par l'augmentation de la cadence des processeurs. La parallélisation des algorithmes 
%est donc un défi majeur dans le cadre des implémentations efficaces pour le futur. De plus, dans 
%certains algorithmes tels que le calcul de la structure de groupe ou de logarithmes discrets, 
%la création de la matrices des relations est trivialement parallélisable tandis que sa mise en forme canonique de Hermite ou de Smith, 
%suivant l'usage qui est fait, est beaucoup moins évidente. Ainsi, les calculs d'algèbre linéraire en 
%général sont l'obstruction majeure à une parallélisation efficace des algorithmes de calculs d'index 
%pour la théorie algorithmique des nombres et la cryptologie.
Nowadays, increasing the capacity of machine is done by adding more cores rather than augmenting the 
frequency of the processors. Therefore, the parallelization of the algorithms is a major challenge 
in the context of efficient implementation for the future. Moreover, in certain algorithms such as 
group structure computation or discrete logarithm computation, the creation of a relation matrix is 
trivially parallelizable while the computation of a canonical form of Hermite or Smith is much 
harder. This way, linear algebra algorithms in general are usually the major obstruction to an 
efficient parallelization of index calculus algorithms for algorithmic number theory and 
cryptology.

%Toutefois, des études ont été menées dans le but de paralléliser la mise en forme de Hermite et de 
%Smith d'une matrice. Ainsi, des versions parallèles de la SNF et de la HNF pour les matrices à 
%coefficients polynomiaux ont été décrites notamment 
%dans~\cite{Kaltofen_SNF_par, Wagner_SNF_par}. Elles reposent sur la possibilité de calculer le PGCD 
%de polynômes en parallèle. Aussi, dans le cadre des matrices dans $\Z$, le calcul du déterminant d'une 
%matrice carrée peut se faire modulo plusieurs nombres premiers en parallèle avant d'être reconstruit par 
%restes chinois. Cette méthode a été utilisée notamment dans le cadre du calcul d'index~\cite{JacobsonPhd} 
%afin d'accélérer les calculs de HNF et de SNF. 
However, the parallelization of the Hermite and Smith normal form has been studied. Indeed, parallel versions of 
the SNF and HNF computation for polynomial matrices were described in~\cite{Kaltofen_SNF_par, Wagner_SNF_par}. 
They rely on the possibility to calculate the GCD of polynomials in parallel. Also, in the context of matrices 
over $\Z$, the computation of the determinant of a square matrix can be done modulo several prime numbers in 
parallel and then reconstructed by the Chinese Remainder Theorem. This method was used in particular in 
index calculus algorithms~\cite{JacobsonPhd} to improve HNF and SNF computations.  


%Une des directions vers lesquelles je compte m'orienter pour améliorer l'état de l'art sur $\Z$ est 
%celle des stratégies récursives par blocs. Pour cela, il faut notamment disposer de méthodes parallèles 
%pour la multiplication des blocs. La multiplication de matrices parallèle génère actuellement beaucoup d'intérêt, et les 
%algorithmes actuels ne permettent pas encore de diviser le temps par le nombre 
%de coeurs disponibles. Cet état de fait a notamment été mis en évidence à la conférence PASCO 2010 durant 
%laquelle une compétition entre les différentes implantations de multiplication parallèle de matrices sur 
%les entiers s'est tenue. Beaucoup de moyens sont actuellement mis en oeuvre pour combler ce manque car 
%c'est un domaine porteur pour les années à venir.  
One of the directions that I intend to take to improve the state of the art is the one of recursive 
block strategies. For that purpose, one needs to use efficient parallel methods for multiplying blocks, 
and a good synchronization of the processes. The parallel multiplication of matrices currently draws a 
lot of attendtion, and the available algorithms do not allow to divide the time by the number of cores 
yet. This fact was highlighted at the PASCO 20120 conference during which a parallel matrix multiplication 
competition took place. A lot of resources are devoted to fill this void since this is a promising 
domain for the years to come.  



\section{Complex multiplication}

%La théorie de la multiplication complexe est un trait d'union entre les résultats obtenus durant 
%ma thèse en théorie algorithmique des nombres et l'étude des courbes algébriques. Plus 
%particulièrement, la théorie de la multiplication complexe identifie l'anneau d'endomorphismes 
%de $\jac$ pour certaines $\courbe$ dites dotées de la multiplication complexe (courbe CM) à un 
%ordre dans un corps de nombres
%$$\operatorname{End}(\jac)\simeq \OO.$$
%De plus, étant données deux courbes munie de multiplication complexe $\courbe_1$ et $\courbe_2$ 
%sur un corps fini , la théorie de la multiplication complexe permet la construction explicite 
%d'isogénies $$\varphi : \courbe_1\longrightarrow\courbe_2,$$
%induisant un morphisme $\jactwo\rightarrow\jacone$. En particulier, le problème du logarithme 
%discret dans $\jactwo$ se réduit réduit au même problème sur $\jacone$. C'est une des raisons 
%pour lesquelles le calcul d'isogénies est le sujet d'études intenses de la part de la communauté 
%cryptographique. Une isogénie est une application rationnelle, et plus son degré est élevé, 
%plus il est difficile de la calculer. Le calcul d'isogénies de large degré est donc un défi 
%important. L'étude de $\operatorname{End}(\jac)$ est aussi important dans la construction de 
%courbes had-oc pour un usage cryptographique. Elle permet notamment de contrôler le nombre de 
%points des courbes facilement, et \textit{in fine} la construction de courbes adaptées aux 
%couplages qui sont appliqués dans le context de la cryptographie basée sur l'identité \og 
%identity based encryption \fg. 
The theory of complex multiplication is a link between the results on algorithmic number theory that 
I obtained during my thesis and the study of algebraic curves. More precisely, complex multiplication 
theory identifies the endomorphism ring of $\jac$ for certain curves said to have ``complex multiplication''
with an order in a number field: 
$$\operatorname{End}(\jac)\simeq \OO.$$
Furthermore, given two curves with complex multiplication $\courbe_1$ and $\courbe_2$ over a finite field, 
the theory of complex multiplication allows the explicit construction of isogenies 
$$\varphi : \courbe_1\longrightarrow\courbe_2,$$
inducing, when they exist, a morphisms $\jactwo\rightarrow\jacone$. In particular, the discrete logarithm problem in $\jactwo$
reduces to the same problem in $\jacone$. This is one of the reasons why isogeny computation is the 
subject of intense studies amongst the cryptographic community. An isogeny is a rational map, and the 
larger its degree, the harder it is to compute. The computation of large degree isogenies is therefore 
an important challenge. The study of $\operatorname{End}(\jac)$ is also important in the construction 
of curves for cryptographic use. In particular, it allows us to easily control the number of points, 
and \textit{in fine}, the construction of paring-friendly curves that are applied in the context of 
``identity-based encryption''. 

\paragraph{Elliptic curves}

%Le cas des courbes elliptiques est le plus facile à traiter car on peut se ramener à des 
%calculs dans un ordre quadratique pour lequel l'utilisation de représentations à l'aide 
%de formes quadratiques permet des calculs optimisés. Ainsi, étant donnée une courbe 
%elliptique $E$ sur un corps fini, son anneau d'endomorphismes satisfait 
%$$\operatorname{End}(\jac)\simeq \OO$$
%pour un certain ordre $\Z[\pi]\subseteq\OO\subseteq\OK$ où $\pi$ est le Frobenius et $\OK$ l'ordre 
%maximal de $K:= \Q(\sqrt{\pi})$. Bisson et Sutherland~\cite{BisSut09} ont montré comment
%calculer $\OO$ à partir de relations dans $\Cl(\OO')$ pour $\Z[\pi]\subseteq \OO'\subseteq \OK$. 
%Les méthodes qu'ils ont utilisées sont beaucoup plus lentes que celles basées sur le crible 
%quadratique que j'ai employées dans~\cite{biasse_quad,BiaJac10,BiaJacSil10}. De même, le 
%calcul explicite d'isogénies de large degré entre deux courbes elliptiques de même anneau 
%d'endomorphisme se fait par identification 
%$$\left(\varphi:E_1\rightarrow E_2\right) \longleftrightarrow \ag_{\varphi}\in \Cl(\OO),$$ 
%où $\OO \simeq \operatorname{End}(E_i)$. Une isogénie de large degré correspond à la classe 
%d'un idéal de large norme dans $\Cl(\OO)$. Br{\"o}ker, Charles et Lauter~\cite{BCL} ont 
%décrit comment décomposer cet idéal comme produit d'idéaux de plus faible norme afin de 
%réduire la difficulité du calcul, mais à l'instar de Bisson et Sutherland~\cite{BisSut09}, 
%ils n'ont pas fait usage des méthodes basées sur le crible quadratique~\cite{biasse_quad,BiaJac10,BiaJacSil10} 
%qui, selon toute vraisemblance, devraient permettre de réaliser des améliorations 
%considérables. Ainsi, malgrès le fait que le genre 1 ait été étudié en profondeur ces 
%dernière années, je pense que les méthodes dédiées pour les corps quadratiques apporteront 
%des améliorations pratiques qui feront une grande différence dans les implantations.
The case of the elliptic curves is the easiest to treat because we can reduce it to computations 
in a quadratic order in which the use of quadratic form representations allows optimized 
operations. This way, given an elliptic curve $E$ over a finite field, $\operatorname{End}(E)$ 
satisfies 
$$\operatorname{End}(E)\simeq \OO,$$
for a certain order $\Z[\pi]\subseteq\OO\subseteq\OK$ where $\pi$ is the Frobenius endomorphisme and 
$\OK$ the maximal order of $K := \Q(\sqrt{\pi})$. Bisson and Sutherland~\cite{BisSut09} showed 
how to compute $\OO$ from relations in $\Cl(\OO')$ for $\Z[\pi]\subseteq \OO'\subseteq \OK$. 
The methods they used are much slower than those based on the quadratic sieve that I used 
in~\cite{biasse_quad,BiaJac10,BiaJacSil10}. In the meantime, the explicit computation of isogenies of 
a large degree between two elliptic curves having the same endomorphism ring can be done by identifying 
$$\left(\varphi:E_1\rightarrow E_2\right) \longleftrightarrow \ag_{\varphi}\in \Cl(\OO),$$
where $\OO \simeq \operatorname{End}(E_i)$. A large degree isogeny corresponds to the class of an ideal 
of large norm in $\Cl(\OO)$. Br{\"o}ker, Charles and Lauter~\cite{BCL} described how to decompose such an 
ideal as a power-product of ideals of smaller norms to reduce the difficulty of the computation, but 
like Bisson and Sutherland~\cite{BisSut09}, they did not used quadratic 
sieve-based methods~~\cite{biasse_quad,BiaJac10,BiaJacSil10} which should most likely allow 
significant improvements. Therefore, despite the fact that genus 1 curves have already been extensively 
studied, I think that methods based on quadratic number fields will provide practical improvements that 
will make a great difference in the implementations.


\paragraph{Genus $g\geq 2$}

%La théorie de la multiplication complexe peut être appliquée aux variétés abéliennes 
%en général, et plus particulièrement aux courbes hyperelliptiques de genre $g\geq 2$ 
%(c'est à dire non elliptiques). Dans ce cas, si l'algèbre 
%$$\Q\otimes\jac$$
%contient un corps de nombres $K$ de degré $2g$, on dit que $\jac$ admet une 
%\textit{multiplication complexe} par le corps $K$. Les cas des courbes elliptiques 
%est ajourd'hui très bien balisé, mais il n'en est pas de même pour le genre 2, et 
%\textit{a foriori} pour $g > 2$. La principale raison est que la théorie est 
%beaucoup plus compliquée, mais aussi car l'état de l'art ne permet pas encore 
%de rejoindre les performances du cas elliptique. Aujourd'hui, le genre 2 préoccupe 
%de nombreux chercheurs dans le domaine car outre le désir de compléter l'étude de 
%l'anneau d'endomorphisme et des isogénies entre courbes à multiplication complexe, 
%il existe aussi un espoir de réaliser des opérations arithmétiques de manière plus 
%efficace dans la Jacobienne d'une courbe de genre $g\geq 2$. 
The theory of complex multiplication can be applied to Abelian varieties in general, 
and more specifically to hyperelliptic curves of genus $g\geq 2$ (that is to say 
non elliptic). In this case, if the algebra 
$$\Q\otimes\jac$$
contains a number field $K$ of degree $2g$, then we say that $\jac$ has 
\textit{complex multiplication} by the field $K$. The case of elliptic curves is now 
well understood, but the same is not true for genus 2 curves, and $\textit{a fortiori}$ 
for $g > 2$. The main reason is that the theory is more involved, but also because the 
state of the art doesn't allow to reach the performances of the elliptic case. The case of 
genus 2 currently preocupies many researchers in the domain since in addition to the desire 
of completing the study of the endomorphism ring and of the isogenies between complex 
multiplication curves, there is also hope to achieve more efficient arithmetic operations 
in the Jacobian of curves with genus $g \leq 2$. 


%Les difficultés techniques sont considérables, notamment à cause de la difficulité 
%de calculer les polynômes modulaires, donnée essentielle pour calculer les isogénies 
%entre courbes de manière directe (sans passer par une décomposition telle que décrite 
%dans~\cite{BCL}). Ainsi, les calculs dans $\Cl(\OO)$, où $\OO\subseteq \OK$ sont plus 
%difficiles car il faut faire apparaître des relations impliquant des idéaux de faible 
%norme, ce qui est une contrainte importante. Une piste pour les rendre plus efficace 
%est l'utilisation de méthodes dédiées pour les corps de faibles degrés, à l'image de 
%ce qui est faisable dans les 
%corps quadratiques. J'ai décrit un algorithme de crible algébrique pour le calcul 
%de relations dans $\Cl(\OO)$ qui s'est révélé très efficace lorsque la dimension de 
%$K$ est petite (typiquement $n\leq 7$). Une adaptation de cette méthode dans le cadre 
%du calcul d'endomorphisme et d'isogénie est susceptible de porter ses fruits pour les 
%genre $g=2,3$ (c'est à dire correspondant à des corps de degré 4 ou 6). Une méthode 
%alternative est la description d'une arithmétique dédiée plus rapide que les algorithmes 
%standards dans les corps de nombres de degrés arbitraire, à l'image de ce qui a été fait 
%pour les corps quadratiques avec l'usage de l'arithmétique sur les formes quadratiques. 
%Enfin, une troisième voie consiste en la recherche de meilleurs invariants pour les 
%calculs de polynômes modulaires. Par exemple, pour les courbes elliptiques, deux courbes 
%$E_1$ et $E_2$ sont reliées par une isogénie de degré $l$ si 
%$$\Phi_l(j(E_1),j(E_2))=0,$$
%où $j(E)$ dénote le $j$-invariant de $E$ et $\Phi_l$ le $l$-ième polynôme modulaire. 
%Br\"{o}ker, Lauter et Sutherland ont montré dans~\cite{drew_mod_pol} que l'usage 
%de polynomes modulaires pour d'autres invariants pouvait réduire les temps de calcul 
%de manière significative. Une telle stratégie se généralise certainment au cas $g\geq 2$, 
%permettant ainsi de surmonter en partie les difficultés liées aux genres supérieurs.
There are considerable technical difficulties, in particular because of the hardness of 
computing modular polynomials, which are essential to directly evaluating isogenies between 
curves (without having to decompose them as described in~\cite{BCL}). This way, computations 
in $\Cl(\OO)$, where $\OO\subseteq \OK$, are harder since we need relations involving ideals 
of small norm. which is an important constraint. One way of making this more efficient is 
to use dedicated methods for low degree fields, in a similar way to what is done in the 
case of quadratic fields. I described an algorithm based on the number field sieve to 
derive relations in $\Cl(\OO)$ which proves itself to be very efficient when the degree of 
$K$ is small (typically $n\leq 7$). An adaptation of this method in the context of endomorphism 
ring and isogeny computation is likely to be fruitful for genus $g=2,3$ (that is to say for 
curves corresponding to fields of degree 4 or 6). An alternative method is the description of 
dedicated algorithms for the arithmetic in field of low degree. Indeed, in 
the quadratic case, a significant speed-up is achieved by using the arithmetic on quadratic forms. 
Finally, a third way consists of searching for better invariants for computing modular polynomials. 
For example, in the genus 1 case, two curves $E_1$ and $E_2$ are linked with a degree $l$ isogeny 
if 
$$\Phi_l(j(E_1),j(E_2))=0,$$
where $j(E)$ denotes the $j$-invariant of $E$ and $\Phi_l$ the $l$-th modular polynomial. 
Br\"{o}ker, Lauter and Sutherland showed in~\cite{drew_mod_pol} that the use of modular polynomials 
for other invariants could significantly reduce the expected time. Such a strategy is likely to 
generalize to $g\geq 2$, thus allowing to partly overcome the difficulty induced by a higher genus.



\section{Conclusion}

%Mon programme de recherche, motivé par les aspects de théorie des nombres de la cryptologie, 
%couvre divers sujets relevant du calcul formel. C'est un programme en lien avec mes travaux 
%antérieurs, comportant des axes de recherche à court, moyen et long terme.  
My research plan, motivated by number theoretical aspects of cryptology, covers various subjects 
related to computed algebra. It is a program linked to my past work that involves research axes for the 
projects, middle and long term. 

\bibliography{programme}

\end{document}